#include <iostream>
#include <string>
#include "linearlist.h"

// Node structure
template< typename T>
struct chainNode
{
    // data 
    T element;
    chainNode<T> *next;

    // method
    chainNode(){};
    chainNode(const T& element)
    {
        this->element = element;
    }
    chainNode(const T& element, chainNode<T>* next)
    {
        this->element = element;
        this->next = next;
    }
};

// chain class
template<typename T>
class Chain: public LinearList<T>
{
public:
    Chain(int initialCapacity = 10){
        if(initialCapacity < 0){
            std::cerr<<"Initial capacity "<<initialCapacity<<" must be > 0"<<std::endl;
            return ;
        }
        m_first_node = nullptr;
        m_size = 0;
    }

    Chain(const Chain<T>& chain){
        m_size = chain.m_size;
        if(m_size == 0){
            m_first_node = nullptr;
            return ;
        }

        // copy all node
        // Step 1: copy head
        chainNode<T>* s = chain.m_first_node;
        m_first_node = new chainNode<T>(s->element);
        // Step 2: move next
        s = s->next;
        chainNode<T>* t = m_first_node;

        // Step 3: loop
        while (s != nullptr)
        {
            t->next = new chainNode<T>(s->element);
            s = s->next;
            t = t->next; 
        }

        // Step 4: end copy
        t->next = nullptr;
    }

    ~Chain(){};

    // ADT
    bool empty()const{return m_size == 0;}

    int size()const{return m_size;}

    T& get(int theIndex)const{
        if(outOfRange(theIndex)){
            return static_cast<T>(-1);
        }
        chainNode<T> * node = m_first_node;
        for(int i = 0; i < theIndex; ++i){
            node = node->next;
        }
        return node->element;
    }

    int indexOf(const T& theElement)const{
        chainNode<T>* node = m_first_node;
        for(int i = 0; i < m_size; ++i){
            if(node->element == theElement){
                return i;
            }else{
                node = node->next;
            }
        }
        return -1;
    }
    
    void erase(int theIndex){
        if(outOfRange(theIndex)){
            std::cerr<<"out of range"<<std::endl;
            return;
        }
        
        chainNode<T>* deleteNode;
        if(theIndex == 0){
            deleteNode = m_first_node;
            m_first_node = m_first_node->next;
        }else{
            // find the node before delete index
            chainNode<T>* p = m_first_node;
            for(int i = 0; i < theIndex - 1; ++i){
                p = p->next;
            }
            // set delete node
            deleteNode = p->next;
            p->next = p->next->next;

        }
        m_size--;
        delete deleteNode;
    }

    void insert(int theIndex, const T& theElement){
        if(outOfRange(theIndex)){
            std::cerr<<"Out of range"<<std::endl;
            return;
        }
        if(theIndex == 0){
            m_first_node = new chainNode<T>(theElement, m_first_node);
        }else
        {
            chainNode<T>* node = m_first_node;
            for(int i = 0; i < theIndex - 1; ++i){
                node = node->next;
            }

            node->next = new chainNode<T>(theElement, node->next);
        }
        m_size++;
    }

    void output(std::ostream& out)const{
        for(chainNode<T>* node; node!=nullptr; node=node->next){
            out<< node->element<<" ";
        }
    }

protected:
    bool outOfRange(int theIndex)const{
        return (theIndex < 0 || theIndex >= m_size);
    }
    int m_capacity;
    int m_size;
    chainNode<T>* m_first_node;

};

template<typename T>
std::ostream& operator<<(std::ostream& out, const Chain<T>& x){
    x.output(out);
    return out;
}

// struct using to bin sort
//struct studentRecord
//{
//    int score;
//    std::string* name;

//    studentRecord(int s){
//        score = s;
//    }

//    int operator !=(const studentRecord& x)const{
//        return (score != x.score);
//    }
//    operator int()const {return score;}

//};

//std::ostream& operator<<(std::ostream& out, const studentRecord& x)
//{
//    out<<x.name<<" "<<x.score<<std::endl;
//    return out;
//}

//void binSort(Chain<studentRecord>& theChain, int range)
//{
//    // Step 1: init for bin
//    Chain<studentRecord>* bins;
//    bins = new Chain<studentRecord>[range + 1];

//    // Step 2: move chain node to bin
//    int n = theChain.size();
//    for(int i = 0; i < n; ++i){
//        studentRecord x = theChain.get(0);
//        theChain.erase(0);
//        bins[x.score].insert(0, x);
//    }

//    // Step 3: linked all bin to chain
//    for(int j = range; j >=0; --j){
//        while (!bins[j].empty()) {
//            studentRecord x = bins[j].get(0);
//            bins[j].erase(0);
//            theChain.insert(0, x);
//        }
//    }

//    // Step 4: delete bin
//    delete [] bins;

//}

int main(int argc, char const *argv[])
{
    /* code */
    return 0;
}
